Slater's condition

In mathematics, Slater's condition (or Slater condition) is a sufficient condition for strong duality to hold for a convex optimization problem. This is a specific example of a constraint qualification. In particular, if Slater's condition holds for the primal problem, then the duality gap is 0, and if the dual value is finite then it is attained.^[1]

Mathematics

Given the problem

$\text{Minimize }\; f_0(x)$

$\text{subject to: }\$

$f_i(x) \le 0 , i = 1,\ldots,m$

$Ax = b$

with $f_0,\ldots,f_m$ convex (and therefore a convex optimization problem). Then strong duality holds if there exists an $x \in \operatorname{relint}(D)$ (where relint is the relative interior and $D = \cap_{i = 0}^m \operatorname{dom}(f_i)$ ) such that

$f_i(x) < 0, i = 1,\ldots,m$ and

$Ax = b.\,$ ^[2]

If the first $k$ constraints, $f_1,\ldots,f_k$ are linear functions, then strong duality holds if there exists an $x \in \operatorname{relint}(D)$ such that

$f_i(x) \le 0, i = 1,\ldots,k,$

$f_i(x) < 0, i = k%2B1,\ldots,m,$ and

$Ax = b.\,$ ^[2]

Generalized Inequalities

Given the problem

$\text{Minimize }\; f_0(x)$

$\text{subject to: }\$

$f_i(x) \le_{K_i} 0 , i = 1,\ldots,m$

$Ax = b$

where $f_0$ is convex and $f_i$ is $K_i$ -convex for each $i$ . Then Slater's condition says that if there exists an $x \in \operatorname{relint}(D)$ such that

$f_i(x) <_{K_i} 0, i = 1,\ldots,m$ and

$Ax = b$

then strong duality holds.^[2]

References

^ Borwein, Jonathan; Lewis, Adrian (2006). Convex Analysis and Nonlinear Optimization: Theory and Examples (2 ed.). Springer. ISBN 9780387295701.
^ ^a ^b ^c Boyd, Stephen; Vandenberghe, Lieven (2004) (pdf). Convex Optimization. Cambridge University Press. ISBN 9780521833783. http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf. Retrieved October 3, 2011.